package middle;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;

public class Solution_377 {

    public static void main(String[] args) {
        Solution_377 model = new Solution_377();
        System.out.println(model.combinationSum4(new int[]{1,2,3}, 4));
        System.out.println(model.combinationSum4(new int[]{9}, 3));
    }

    public int combinationSum4(int[] nums, int target) {
        Arrays.sort(nums);
        int[] counts = new int[target + 1];
//        List<List<Integer>>[] arrays = new List[target + 1];
        for (int i = 1; i <= target; i++) {
            List<List<Integer>> now_lists = null;
            for (int j = 0; j < nums.length; j++) {
                if (j > 0 && nums[j] == nums[j - 1]) {
                    continue;
                }
                int num = nums[j];
                if (num > i) {
                    break;
                } else if (num == i) {
                    counts[i]++;
//                    List<List<Integer>> lists = arrays[i];
//                    if (lists == null) {
//                        lists = new ArrayList<>();
//                    }
//                    List<Integer> list = new ArrayList<>();
//                    list.add(num);
//                    lists.add(list);
//                    arrays[i] = lists;
                } else {
//                    List<List<Integer>> lists = arrays[i - num];
                    counts[i] += counts[i-num];
//                    if (lists == null || lists.size() == 0) {
//                        continue;
//                    }
//                    if (now_lists == null) {
//                        now_lists = new ArrayList<>();
//                        arrays[i] = now_lists;
//                    }
//                    for (List<Integer> list : lists) {
//                        List<Integer> clone = new ArrayList<>(list);
//                        clone.add(num);
//                        now_lists.add(clone);
//                    }
                }
            }
        }
//        int count = 0;
//        List<List<Integer>> lists = arrays[target];
//        for (List<Integer> list : lists) {
//            Collections.sort(list);
//            int pre_index = 0, divide = 1;
//            for (int i = 1; i < list.size(); i++) {
//                if (!list.get(i).equals(list.get(pre_index))) {
//                    divide *= jie(i - pre_index);
//                    pre_index = i;
//                }
//            }
//            divide *= jie(list.size() - pre_index);
//            count += (jie(list.size()) / divide);
//        }
        return counts[target];
    }

    private int jie(int n) {
        int r = n;
        while (n-- > 0) {
            r *= n;
        }
        return r;
    }
}
